25. 矩阵螺旋遍历

题目内容

给定一个 M 行 N 列的矩阵，矩阵中每个元素是一个非负整数。从左上角 (0, 0) 开始，按顺时针螺旋顺序遍历矩阵，对于遍历到的每个数字，计算其二进制表示中 1 的个数，如果 1 的个数是 3 的倍数，则记录该数字的坐标。请按照顺序输出满足条件的数字的坐标列表。

螺旋遍历按照从外到内进行，从 (0, 0) 出发先向右，遇到边界或已访问元素后，按 右 → 下 → 左 → 上 的顺序循环转向。

输入描述

输入共 M + 1 行：

• 第一行：两个整数 M、N，表示矩阵的行数和列数
• 接下来 M 行：每行 N 个非负整数，即二维数组 Array[M][N]，整数范围 0 ≤ 元素值 ≤ 10^9

输出描述

按遍历顺序输出满足条件的坐标，单个坐标的格式为 (行索引,列索引)，坐标之间以空格分隔；如果没有满足条件的数字则输出空。

注意：数字 0 的二进制表示中 1 的个数为 0，0 是 3 的倍数，因此数字 0 按满足条件统计输出。

样例

样例 1

输入

3 4
1 2 3 4
5 6 7 8
9 10 11 12

输出

(2,2) (1,2)

说明： 螺旋遍历顺序为：

(0,0)=1 → (0,1)=2 → (0,2)=3 → (0,3)=4 → (1,3)=8 → (2,3)=12 → (2,2)=11 → (2,1)=10 → (2,0)=9 → (1,0)=5 → (1,1)=6 → (1,2)=7

其中二进制表示中 1 的个数是 3 的倍数的数字：

• 11 = 1011(2)，有 3 个 1，坐标 (2,2)
• 7 = 111(2)，有 3 个 1，坐标 (1,2)

按遍历顺序输出 (2,2) (1,2)。

代码

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

let inputs = [];
rl.on('line', (input) => {
    inputs.push(input.split(' ').map(Number));
})
rl.on('close', () => {
    const [m, n] = inputs.shift();
    const list = inputs;
    const used = Array.from({ length: m }, () => Array.from({ length: n }, () => false));
    const ans = [];

    const dfs = (x, y, t) => {
        // 关键：进入时先检查，防止重复
        if (x < 0 || x >= m || y < 0 || y >= n || used[x][y]) {
            return;
        }

        used[x][y] = true;
        const val = list[x][y];

        // 统计二进制中 1 的个数
        const len = val.toString(2).split('').filter(c => c === '1').length;
        if (len % 3 === 0) {
            ans.push(`(${x},${y})`);
        }

        if (t === 'r') {
            if (y + 1 < n && !used[x][y + 1]) {
                dfs(x, y + 1, 'r');
            } else if (x + 1 < m && !used[x + 1][y]) {
                dfs(x + 1, y, 'd');
            }
        } else if (t === 'd') {
            if (x + 1 < m && !used[x + 1][y]) {
                dfs(x + 1, y, 'd');
            } else if (y - 1 >= 0 && !used[x][y - 1]) {
                dfs(x, y - 1, 'l');
            }
        } else if (t === 'l') {
            if (y - 1 >= 0 && !used[x][y - 1]) {
                dfs(x, y - 1, 'l');
            } else if (x - 1 >= 0 && !used[x - 1][y]) {
                dfs(x - 1, y, 'u');
            }
        } else if (t === 'u') {
            if (x - 1 >= 0 && !used[x - 1][y]) {
                dfs(x - 1, y, 'u');
            } else if (y + 1 < n && !used[x][y + 1]) {
                dfs(x, y + 1, 'r');
            }
        }
    }

    dfs(0, 0, 'r');
    console.log(ans.join(' '));
});